public class Code1 {
    // 使用最小花费爬楼梯
    public int minCostClimbingStairs1(int[] cost) {
        // 1、 创建 dp 表
        // 2、 初始化
        // 3、 填表
        // 4、 返回值

        // 解法一，从前向后获取最小值
        // 这里写的是 动态规划方式解决的第一种方法

        // 这里需要多加一位，因为台阶到达最后一阶时，还得向上才能登顶
        int n = cost.length;
        int[] dp = new int[n + 1];
        // 这里从 2 起步就是进行了初始化操作 dp[i - 2] 正好需要空出来两个位置

        for(int i = 2; i <= n; i++){
            dp[i] = Math.min(dp[i-1] + cost[i -1],dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }

    public int minCostClimbingStairs2(int[] cost) {
        // 1、 创建 dp 表
        // 2、 初始化
        // 3、 填表
        // 4、 返回值

        // 解法二，从后向前获取最小值
        // 上一种解法是 dp 表不断地从前向后加和获取到最终最小的 dp[n]
        // 这道题的解法与第一种的方法相反

        int n = cost.length;
        // 因为是倒着向前加和最小值，这里的数组到 n 就足够了
        int[] dp = new int[n];
        // 对 dp 表的后两位置进行初始化
        dp[n - 1] = cost[n - 1];
        dp[n - 2] = cost[n - 2];
        for(int i = n - 3; i >= 0 ; i--){
            dp[i] = Math.min(dp[i + 1],dp[i + 2]) + cost[i];
        }
        return Math.min(dp[0],dp[1]);
    }
}
